package org.lql.algo.codecrush.hot100.binaryTree;

import org.lql.algo.common.TreeNode;

/**
 * @author: liangqinglong
 * @date: 2025-09-07 16:48
 * @description: 114. 二叉树展开为链表 <a href="https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 **/
public class Flatten {

	public void flatten(TreeNode root) {
		TreeNode current = root;
		while (current != null) {
			// 存在左子树
			if (current.left != null) {
				// 记录当前左子节点
				TreeNode next = current.left;
				// 前驱节点，即当前的左子节点，用于后续遍历
				TreeNode pre = next;
				// 遍历查找左子树的最右子节点
				while (pre.right != null) {
					pre = pre.right;
				}
				pre.right = current.right;
				// 将当前节点的左指针置为空
				current.left = null;
				// 将当前节点的右指针指向左子树
				current.right = next;
			}
			current = current.right;
		}
	}

	public void flatten1(TreeNode root) {
		if (root == null) {
			return;
		}
		flatten1(root.left);
		flatten1(root.right);
		if (root.left != null) {
			TreeNode tmp = root.right;
			root.right = root.left;
			root.left = null;
			TreeNode pre = root.right;
			while (pre.right != null) {
				pre = pre.right;
			}
			pre.right = tmp;
		}
	}

	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(5);
		root.left.left = new TreeNode(3);
		root.left.right = new TreeNode(4);
		root.right.right = new TreeNode(6);
		new Flatten().flatten(root);
	}
}
